package leetcode.dynamic;

/**
 * 给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。
 * <p>
 * 对于每个单元格，你可以往上，下，左，右四个方向移动。 你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：matrix = [[9,9,4],[6,6,8],[2,1,1]]
 * 输出：4
 * 解释：最长递增路径为 [1, 2, 6, 9]。
 * 示例 2：
 * <p>
 * <p>
 * 输入：matrix = [[3,4,5],[3,2,6],[2,2,1]]
 * 输出：4
 * 解释：最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。
 * 示例 3：
 * <p>
 * 输入：matrix = [[1]]
 * 输出：1
 * <p>
 * <p>
 * 提示：
 * <p>
 * m == matrix.length
 * n == matrix[i].length
 * 1 <= m, n <= 200
 * 0 <= matrix[i][j] <= 231 - 1
 */
public class LeetCode329_LongestIncreasingPath {
    public int longestIncreasingPath(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                ans = Math.max(ans, f(m, n, matrix, i, j));
            }
        }
        return ans + 1;
    }

    public int f(int m, int n, int[][] matrix, int i, int j) {
        if (i < 0 || j < 0 || i >= m || j >= n) {
            return 0;
        }

        int ans1 = 0;
        int ans2 = 0;
        int ans3 = 0;
        int ans4 = 0;

        if (i + 1 < m && matrix[i + 1][j] > matrix[i][j]) {
            ans1 = f(m, n, matrix, i + 1, j) + 1;
        }

        if (i - 1 >= 0 && matrix[i - 1][j] > matrix[i][j]) {
            ans2 = f(m, n, matrix, i - 1, j) + 1;
        }

        if (j + 1 < n && matrix[i][j + 1] > matrix[i][j]) {
            ans3 = f(m, n, matrix, i, j + 1) + 1;
        }

        if (j - 1 >= 0 && matrix[i][j - 1] > matrix[i][j]) {
            ans4 = f(m, n, matrix, i, j - 1) + 1;
        }

        return Math.max(Math.max(ans1, ans2), Math.max(ans3, ans4));
    }
}
